/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution289 {

    public static void main(String args[]){
        Solution289 s = new Solution289();
    }

    public void gameOfLife(int[][] board) {
        int n = board.length;
        int m = board[0].length;
        for(int i = 0; i < n ; i ++){
            for(int j = 0 ; j < m ; j ++){
                board[i][j] = board[i][j] << 1;
            }
        }

        for(int i = 0 ; i < n ; i ++){
            for(int j = 0 ; j < m ; j ++){
                int cnt = count(board, i, j, n, m);
                if((board[i][j] >> 1) == 1){
                    if(cnt == 2 || cnt == 3){
                        board[i][j] ^= 1;
                    }
                }else if(cnt == 3){
                    board[i][j] ^= 1;
                }
            }
        }
        for(int i = 0; i < n ; i ++){
            for(int j = 0 ; j < m ; j ++){
                board[i][j] &= 1;
            }
        }

    }

    public int count(int[][] board, int x, int y, int n, int m){
        int[] dx = new int[]{0, -1, -1, -1, 0, 1, 1, 1};
        int[] dy = new int[]{-1, -1, 0, 1, 1, 1, 0, -1};
        int cnt = 0;
        for(int i = 0 ; i < 8 ; i ++){
            if(x + dx[i] >= 0 && x + dx[i] < n && y + dy[i] >= 0 && y + dy[i] < m){
                int v = board[x + dx[i]][y + dy[i]];
                cnt += (v >> 1);
            }
        }
        return cnt;
    }

}
